package stu.day49;

import java.util.Arrays;
import java.util.List;

public class hw1 {



    public int networkDelayTime(int[][] times, int n, int k) {


        int[] flag = new int[n];
        Arrays.fill(flag,Integer.MAX_VALUE);


        boolean[][] num = new boolean[n][n];

        for (int[] arr:times){
            num[arr[0]-1][arr[1]-1] = true;
        }

        int num1=0;
        dfs(times,k,flag,num1,1000,num);




        for (int b:flag){
            if(b==Integer.MAX_VALUE){
                return -1;
            }
        }

        int max = 0;
        for (int i=0;i<n;i++){
            if(i!=k-1){
                max = Math.max(max,flag[i]);
            }
        }
        return max;
    }



    public void dfs(int[][] times,int now,int[] flag,int num,int last,boolean[][] num1){

        flag[now-1] = Math.min(flag[now-1],num);

        for (int[] arr:times){
            if(arr[0]==now && arr[1]!=last && num1[arr[0]-1][arr[1]-1]){
                num1[arr[0]-1][arr[1]-1] = false;
                dfs(times,arr[1],flag,num+arr[2],arr[0],num1);
            }
        }

    }




}
